/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-07-28
 * Time: 17:25
 */

import java.util.Arrays;

/**
 * 直接插入排序
 */
public class InsertionSort {

    /**
     * 时间复杂度 : O(N^2) -- 最坏情况下位降序排序然后进行插入排序, 每一次当前位置都需要往前挪动 N - i 个.
     * 空间复杂度为 : O(1)
     * 稳定性 : 一种稳定的排序
     *         TODO : 当插入条件为 array[j] >= tmp 会变成一个不稳定的排序
     *                但是原本不稳定的排序无法变成稳定排序
     *
     * 通常使用在数据量较小, 且已经趋近于有序, 并且越有序排序效率越高
     */
    public void insertSort(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for(; j >= 0; j--) {
                // j 和后一个元素 tmp 进行比较
                // array[j] > tmp
                if(array[j] > tmp) {
                    // 调整位置 小的放到前面
                    array[j + 1] = array[j];

                } else {
                    // 前一个比当前小, 不再需要重新排序放回原位置
                    // array[j + 1] = tmp;
                    // 前面有序的前一个最大的数都比当前这个数小, 说明此时无需再排序
                    break;
                }
            }

            // 走到此时, 如果最后一个数最小, 那么 j 一定会回退到 -1 下标处
            array[j + 1] = tmp;
        }
    }

    public static void main(String[] args) {
        InsertionSort insertionSort = new InsertionSort();
        int[] array = {5, 4, 7, 2};
        insertionSort.insertSort(array);
        System.out.println(Arrays.toString(array));
    }
}
